package com.code.test.second.link;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.md
 * <p>
 * 142.环形链表II
 * 力扣题目链接
 * <p>
 * 题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * <p>
 * 为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 * <p>
 * 说明：不允许修改给定的链表。
 */
public class SCode142 {
    public static void main(String[] args) {
        SNode headA21 = new SNode(21);
        SNode headA22 = new SNode(22);
        SNode headA23 = new SNode(23);
        SNode n4 = new SNode(24);
        SNode n5 = new SNode(99);
        SNode n6 = new SNode(98);
        SNode n7 = new SNode(100);

        headA21.setNext(headA22);
        headA22.setNext(headA23);
        headA23.setNext(n4);


        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);
        n7.setNext(n4);

        SNode circle = detectWithSlow(headA21);
        int a = 2;

    }

    public static SNode detectCycle(SNode head) {
        SNode fast = head;
        SNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            //一个走得快，一个走得慢，有环一定会相遇
            if (fast == slow) {
                //因为存在环，才会让2个快慢的指针相遇
                //有环

                //从相遇节点开始算
                SNode index1 = fast;
                //从头结点开始算
                SNode index2 = head;

                while (index1 != index2) {
                    //2个指针，从头结点和相遇节点，各走一步，一直到相遇，相遇点即为环入口
                    index1 = index1.next;
                    index2 = index2.next;
                }

                return index1;
            }
        }
        return null;

    }


    public static SNode detectWithMap(SNode head) {
        if (head == null) {
            return null;
        }
        Set<SNode> detected = new HashSet<>();
        SNode cur = head;
        while (cur != null) {
            if (!detected.contains(cur)) {
                detected.add(cur);
            } else {
                //有环，且就是当前节点
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    public static SNode detectWithSlow(SNode head) {
        SNode fast = head;
        SNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                //检测到环后,fast继续走X步，跟从头开始走的步数一样，因为有环，所以一定会碰头
                SNode s1 = head;
                while (s1 != fast) {
                    s1 = s1.next;
                    fast = fast.next;
                }
                return s1;
            }
        }

        return null;

    }
}
